
import javax.swing.border.*; //导入用到的包
import javax.swing.*;
import java.util.Vector;
import java.awt.*;
import java.awt.event.*;

/*n皇后探索类
 * 
 * */
class nQueenExplore {

    JPanel resultPane;  //结果面板，用来显示所有棋盘的摆放
    int[] chessboard = new int[20]; //chessboard是一个一维列数组，用来模拟棋盘，因为每一行只能放一个棋子
    //为了方便，规定下标从1开始
    int num, count = 0;  //num是棋盘的行数或者列数，count用来计数有多少种摆法
    long exploreCount = 0;  //探索次数
    boolean isShow;        //是否分步显示,是否绘制棋盘，不绘制的话计算更快
    //类的构造方法，传入参数
    public nQueenExplore(int n, JPanel jPanel, boolean isShow) {
        num = n;
        resultPane = jPanel;
        this.isShow = isShow;
    }

    //方法1，回溯与栈
    public void flashBack_find() {
        int j = 1, h = 1, v = 1; //h,v分别表示当前行和当前列
        /* 栈是用来存上一层可放置位置的列号 */
        MyStack<Integer> stack = new MyStack<Integer>();
        stack.push(v); //先把第一行的，第一列入栈
        chessboard[1] = 1;
        h++;   //进入第下一行，这里是第二行
        while (true) { //永真循环，直到里面检测到栈空时返回
            while (h <= num) {//当前行小于等于num时循环
                for (j = v; j <= num; j++) {  //从当前列开始找一个可以放置的列 j
                    if (check(h, j)) {
                        chessboard[h] = j; //放置皇后，将列号记入栈中
                        stack.push(j);
                        h++;  //并将下一行置成当前行，第1列置为当前列；
                        v = 1;
                        break;  //找到后进入下一行，break
                    }
                }
                if (j > num) {  //某一行找完了，就退栈，去上一行找
                    if (stack.isEmpty())   //栈空时退出
                        return;
                    h--;    //回到上一行
                    v = stack.pop() + 1; //上一行的已经找过的后面开始找
                    chessboard[h] = 0;  //移去该行已放置的皇后
                }
            }
            count++;  //来到这里表示h>num，输出一个结果，计数器加一
            if (isShow) //要求绘制的时候绘制图像
                print();
            h--;  //回到上一行，在这里其实是回到最后一行
            v = stack.pop() + 1;  //上一行的已经找过的后面开始找
            chessboard[h] = 0;  //移去该行已放置的皇后
        }
    }

    //方法2，递归法
    public void recursion_find(int n) {
        if (n > num) {//如果在最后一行找到一个可以放的位置后，就说明这是一个摆法方法了，将其打印出来
            count++;
            if (isShow)
                print();
        } else {
            for (int j = 1; j <= num; j++) {
                if (check(n, j)) { //检查第n行，第j列是否可以放
                    chessboard[n] = j;        //如果可以放的话，则把第n行的棋子放到第j列的位置
                    recursion_find(n + 1);    //继续找下一行
                    chessboard[n] = 0;  //下面找完后，回来，移除当前行
                }
            }
        }
    }

    //方法3，非递归法，自己突发奇想的，基本思想还是回溯
    public void stack_find() {
        int i = 1, j = 1;
        MyStack<int[]> stack = new MyStack<int[]>();  //栈里面存的是一个点，[i,j]代表第i行第j列
        for (j = num; j >= 1; j--)
            stack.push(newPoint(i, j)); //把第一行的全部元素放入栈中，倒序
        while (!stack.isEmpty()) { //栈不空的时候循环
            int[] each = stack.pop(); //取栈顶元素
            if (check(each[0], each[1])) {  //可以放
                chessboard[each[0]] = each[1];   //把棋盘的第each[0]行的棋子，放到第each[1]列上
                if (each[0] == num) {   //如果可以放并且是最后一行，输出
                    count++;
                    if (isShow)
                        print();
                } else {    //不是最后一行则，把下一行入栈
                    i = each[0] + 1;
                    for (j = num; j > each[1] + 1; j--) //这个棋子下面的三个肯定是
                        stack.push(newPoint(i, j));      //不能放的，所以不用放
                    for (j = each[1] - 2; j >= 1; j--)
                        stack.push(newPoint(i, j));
                }
            }
        }
    }
    //返回一个数组表示一个点
    public int[] newPoint(int i, int j) {
        int[] r = new int[2];
        r[0] = i;
        r[1] = j;
        return r;
    }
    //检查
    public boolean check(int i, int j) {
        exploreCount++;  //检查次数加一
        boolean flag = true;
        for (int k = i - 1; k >= 1; k--) {  //从第i-1行开始检查到第一行，看看有没有在同一条线上
            if (j == chessboard[k]) {
                flag = false; //上方有棋子，失败
                break;
            }
            if (Math.abs(i - k) == Math.abs(j - chessboard[k])) {
                //左斜上方或者右斜上方有棋子
                flag = false;
                break;
            }
        }
        return flag;
    }

    public void print() {
        //以新建一个MyPanel添加到结果面板
        resultPane.add(new MyPanel(num, count, chessboard));
    }
}